package com.hr.leetcode.栈与队列;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author 周恒哲
 * @date 2020/05/12
 **/
public class _239_滑动窗口最大值 {

    //暴力法
    public int[] maxSlidingWindow(int[] nums, int k) {
        if ((nums.length) * k == 0) {
            return new int[0];
        }
        int[] max = new int[nums.length - k + 1];
        for (int i = 0; i < nums.length - k + 1; i++) {
            int temp = Integer.MIN_VALUE;
            for (int j = i; j < i + k; j++) {
                temp = Math.max(temp, nums[j]);
            }
            max[i] = temp;
        }
        return max;
    }
    //利用双端队列
    public int[] maxSlidingWindow1(int[] nums, int k) {
        Deque<Integer> window=new ArrayDeque<>(3);
        int n=nums.length;
        if (n*k==0){
            return new int[0];
        }
        if (k==1){
            return nums;
        }
        int max=0;
        //遍历滑动窗口的值
        for (int i=0;i<k;i++){
            //如果队列中值不为空，且头队列值等于
            if (!window.isEmpty()&&window.getFirst()==i-k){
                window.removeFirst();
            }
            while (!window.isEmpty()&&nums[i]>nums[window.getLast()]){
                window.removeLast();
            }
        }
        return new int[0];

    }
}
